home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / x11 / strategy / xpuzzles.3 / xpuzzles / xpuzzles-5.3.1 / xrubik / RubikS.c < prev    next >
C/C++ Source or Header  |  1996-02-05  |  29KB  |  1,139 lines
  1. /*
  2. # X-BASED RUBIK'S CUBE(tm)
  3. #
  4. #  RubikS.c
  5. #
  6. ###
  7. #
  8. #  Taken from code originally written by 
  9. #  Michael B. Martin <martinm@sps1.phys.vt.edu>
  10. #  From cubist10.c-- for IBM PC.
  11. #  Used by permission.
  12. #  Taken from the algorithm in the Ideal Solution book.
  13. #
  14. #  Copyright (c) 1994 - 96    David Albert Bagley, bagleyd@hertz.njit.edu
  15. #
  16. #                   All Rights Reserved
  17. #
  18. #  Permission to use, copy, modify, and distribute this software and
  19. #  its documentation for any purpose and without fee is hereby granted,
  20. #  provided that the above copyright notice appear in all copies and
  21. #  that both that copyright notice and this permission notice appear in
  22. #  supporting documentation, and that the name of the author not be
  23. #  used in advertising or publicity pertaining to distribution of the
  24. #  software without specific, written prior permission.
  25. #
  26. #  This program is distributed in the hope that it will be "playable",
  27. #  but WITHOUT ANY WARRANTY; without even the implied warranty of
  28. #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  29. #
  30. */
  31.  
  32. /* Solver file for Rubik */
  33.  
  34. #include <stdio.h>
  35. #include <X11/IntrinsicP.h>
  36. #include <X11/Intrinsic.h>
  37. #include <X11/StringDefs.h>
  38. #include <X11/CoreP.h>
  39. #include "RubikP.h"
  40. #include "Rubik2dP.h"
  41. #include "Rubik3dP.h"
  42.  
  43. /* Mappings of Ideal notation to my General nxnxn cube notation */
  44. #define RotateLeft(w)    MoveRubik(w,2,0,LEFT,TRUE)
  45. #define RotateRight(w)    MoveRubik(w,2,0,RIGHT,TRUE)
  46. #define RotateUp(w)    MoveRubik(w,2,0,TOP,TRUE)
  47. #define RotateDown(w)    MoveRubik(w,2,0,BOTTOM,TRUE)
  48. #define RotateCw(w)    MoveRubik(w,0,0,RIGHT,TRUE)
  49. #define RotateCcw(w)    MoveRubik(w,0,0,LEFT,TRUE)
  50.  
  51. #define RotateTopLeft(w)    MoveRubik(w,2,0,LEFT,FALSE)
  52. #define RotateCenterLeft(w)    MoveRubik(w,2,w->rubik.size,LEFT,FALSE)
  53. #define RotateBottomLeft(w)    MoveRubik(w,2,w->rubik.size*(w->rubik.size-1),LEFT,FALSE)
  54. #define RotateTopRight(w)    MoveRubik(w,2,0,RIGHT,FALSE)
  55. #define RotateCenterRight(w)    MoveRubik(w,2,w->rubik.size,RIGHT,FALSE)
  56. #define RotateBottomRight(w)    MoveRubik(w,2,w->rubik.size*(w->rubik.size-1),RIGHT,FALSE)
  57. #define RotateLeftUp(w)        MoveRubik(w,2,0,TOP,FALSE)
  58. #define RotateCenterUp(w)    MoveRubik(w,2,1,TOP,FALSE)
  59. #define RotateRightUp(w)    MoveRubik(w,2,w->rubik.size-1,TOP,FALSE)
  60. #define RotateLeftDown(w)    MoveRubik(w,2,0,BOTTOM,FALSE)
  61. #define RotateCenterDown(w)    MoveRubik(w,2,1,BOTTOM,FALSE)
  62. #define RotateRightDown(w)    MoveRubik(w,2,w->rubik.size-1,BOTTOM,FALSE)
  63. #define RotateFrontCw(w)    MoveRubik(w,0,w->rubik.size*(w->rubik.size-1),RIGHT,FALSE)
  64. #define RotateFrontCcw(w)    MoveRubik(w,0,w->rubik.size*(w->rubik.size-1),LEFT,FALSE)
  65.  
  66. #define BLUE 0
  67. #define WHITE 1
  68. #define RED 2
  69. #define YELLOW 3
  70. #define GREEN 4
  71. #define ORANGE 5
  72.  
  73. #ifdef DEBUG
  74. static int mapGeneralToIdeal[MAXFACES]={5, 4, 1, 2, 6, 3};
  75. #endif
  76. static int mapIdealToGeneral[MAXFACES]={2, 3, 5, 1, 0, 4}; /* Remember to subtract 1 */
  77.  
  78. static int Side();
  79. static int FindCorner();
  80. static int FindEdge();
  81. static void PlaceEdge();
  82. static void SolveTop();
  83. static void AlignCorners();
  84. static void SwapBottomCorners();
  85. static void SolveBottom();
  86. static void Solve_2_2();
  87. static void SolveBottomEdges();
  88. static void AlignLastEdge();
  89. static void ColorAlignFront();
  90. static void AlignEdges();
  91. static void ShuffleEdges();
  92. static void RecolorTopEdges();
  93.  
  94. static int Side(w, m, c)
  95.   RubikWidget w;
  96.   int m, c;
  97. {
  98.   int d, i, j;
  99.  
  100.   d = mapIdealToGeneral[m - 1];
  101.   i = c % 3;
  102.   j = c / 3;
  103.   if (i == 2)
  104.     i = w->rubik.size - 1;
  105.   if (j == 2)
  106.     j = w->rubik.size - 1;
  107.   return w->rubik.cubeLoc[d][j * w->rubik.size + i].face;
  108. }
  109.  
  110. /* This procedure finds the location of a specified corner.  An */
  111. /* improperly-specified color combination will result in a return */
  112. /* value of 9. */
  113. static int FindCorner(w, color1, color2, color3)
  114.   RubikWidget w;
  115.   int color1, color2, color3;
  116. {
  117.   int corner = 0, temp = 1;
  118.  
  119.   do {
  120.     if (Side(w, 5, 6) == color1) {
  121.       if (Side(w, 1, 0) == color2)
  122.         if (Side(w, 4, 2) == color3)
  123.           corner = temp;
  124.     } else if (Side(w, 5, 6) == color2) {
  125.       if (Side(w, 1, 0) == color3)
  126.         if (Side(w, 4, 2) == color1)
  127.           corner = temp;
  128.     } else if (Side(w, 5, 6) == color3) {
  129.       if (Side(w, 1, 0) == color1)
  130.         if (Side(w, 4, 2) == color2)
  131.           corner = temp;
  132.     }
  133.  
  134.     if (corner == 0) {
  135.       if (temp < 4)
  136.         RotateLeft(w);
  137.       else if (temp == 4) {
  138.         RotateCw(w);
  139.         RotateCw(w);
  140.       } else if (temp < 8)
  141.         RotateRight(w);
  142.       else if (temp == 8)
  143.         corner = 9;
  144.       temp++;
  145.     }
  146.   } while (corner == 0);
  147.  
  148.   /* put the cube back to the way it was */
  149.   if (corner == 2)
  150.      RotateRight(w);
  151.   else if (corner == 3) {
  152.     RotateRight(w);
  153.     RotateRight(w);
  154.   } else if (corner == 4)
  155.     RotateLeft(w);
  156.   else if (corner == 5) {
  157.     RotateCw(w);
  158.     RotateCw(w);
  159.     RotateLeft(w);
  160.   } else if (corner == 6) {
  161.     RotateCw(w);
  162.     RotateCw(w);
  163.   } else if (corner == 7) {
  164.     RotateCw(w);
  165.     RotateCw(w);
  166.     RotateRight(w);
  167.   } else if (corner == 8) {
  168.     RotateCw(w);
  169.     RotateCw(w);
  170.     RotateRight(w);
  171.     RotateRight(w);
  172.   }
  173.   return(corner);
  174. }
  175.  
  176. /* This procedure finds the location of a specified edge.  An */
  177. /* improperly-specified color combination will result in a return */
  178. /* value of 13. */
  179. static int FindEdge(w, color1, color2)
  180.   RubikWidget w;
  181.   int color1, color2;
  182. {
  183.   int edge = 0, temp = 1;
  184.  
  185.   do {
  186.     if (Side(w, 5, 7) == color1) {
  187.       if (Side(w, 1, 1) == color2)
  188.         edge = temp;
  189.     } else if (Side(w, 5, 7) == color2) {
  190.       if (Side(w, 1, 1) == color1)
  191.         edge = temp;
  192.     }
  193.  
  194.     if (edge == 0) {
  195.       if (temp < 4)
  196.         RotateLeft(w);
  197.       else if (temp == 4) {
  198.         RotateLeft(w);
  199.         RotateCw(w);
  200.       } else if (temp < 8)
  201.         RotateUp(w);
  202.       else if (temp == 8) {
  203.         RotateUp(w);
  204.         RotateCw(w);
  205.       } else if (temp < 12)
  206.         RotateRight(w);
  207.       else if (temp == 12)
  208.         edge = 13;  /* end condition, just in case */
  209.       temp++;
  210.     }
  211.   } while (edge == 0);
  212.  
  213.   /* put the cube back to the way it was */
  214.   if (edge == 2) {
  215.     RotateRight(w);
  216.   } else if (edge == 3) {
  217.     RotateRight(w);
  218.     RotateRight(w);
  219.   } else if (edge == 4) {
  220.     RotateLeft(w);
  221.   } else if (edge == 5) {
  222.     RotateCcw(w);
  223.   } else if (edge == 6) {
  224.     RotateCcw(w);
  225.     RotateRight(w);
  226.   } else if (edge == 7) {
  227.     RotateCcw(w);
  228.     RotateRight(w);
  229.     RotateRight(w);
  230.   } else if (edge == 8) {
  231.     RotateCcw(w);
  232.     RotateLeft(w);
  233.   } else if (edge == 9) {
  234.     RotateCcw(w);
  235.     RotateCcw(w);
  236.   } else if (edge == 10) {
  237.     RotateCcw(w);
  238.     RotateCcw(w);
  239.     RotateRight(w);
  240.   } else if (edge == 11) {
  241.     RotateUp(w);
  242.     RotateUp(w);
  243.   } else if (edge == 12) {
  244.     RotateUp(w);
  245.     RotateUp(w);
  246.     RotateRight(w);
  247.   }
  248.   return(edge);
  249. }
  250.  
  251. /* This procedure places the specified edge piece in edge position */
  252. /* #1 (front top). */
  253. static void PlaceEdge(w, edge, top_color)
  254.   RubikWidget w;
  255.   int edge, top_color;
  256. {
  257.   /* first put the edge piece in position #8 (center row, left rear) */
  258.   if (edge == 1) {
  259.     if (Side(w, 5, 7) == top_color)
  260.       return;  /* already in place */
  261.     else {
  262.       RotateFrontCcw(w);
  263.       RotateCenterLeft(w);
  264.       RotateFrontCw(w);
  265.     }
  266.   } else if (edge == 2) {
  267.     RotateTopLeft(w);
  268.     RotateFrontCcw(w);
  269.     RotateCenterLeft(w);
  270.     RotateFrontCw(w);
  271.     RotateTopRight(w);
  272.   } else if (edge == 3) {
  273.     RotateTopLeft(w);
  274.     RotateTopLeft(w);
  275.     RotateFrontCcw(w);
  276.     RotateCenterLeft(w);
  277.     RotateFrontCw(w);
  278.     RotateTopRight(w);
  279.     RotateTopRight(w);
  280.   } else if (edge == 4) {
  281.     RotateTopRight(w);
  282.     RotateFrontCcw(w);
  283.     RotateCenterLeft(w);
  284.     RotateFrontCw(w);
  285.     RotateTopLeft(w);
  286.   } else if (edge == 5) {
  287.     RotateCenterLeft(w);
  288.   } else if (edge == 6) {
  289.     RotateCenterLeft(w);
  290.     RotateCenterLeft(w);
  291.   } else if (edge == 7) {
  292.     RotateCenterRight(w);
  293.   } else if (edge == 9) {
  294.     RotateFrontCw(w);
  295.     RotateCenterLeft(w);
  296.     RotateFrontCcw(w);
  297.   } else if (edge == 10) {
  298.     RotateBottomLeft(w);
  299.     RotateFrontCw(w);
  300.     RotateCenterLeft(w);
  301.     RotateFrontCcw(w);
  302.     RotateBottomRight(w);
  303.   } else if (edge == 11) {
  304.     RotateBottomLeft(w);
  305.     RotateBottomLeft(w);
  306.     RotateFrontCw(w);
  307.     RotateCenterLeft(w);
  308.     RotateFrontCcw(w);
  309.     RotateBottomRight(w);
  310.     RotateBottomRight(w);
  311.   } else if (edge == 12) {
  312.     RotateBottomRight(w);
  313.     RotateFrontCw(w);
  314.     RotateCenterLeft(w);
  315.     RotateFrontCcw(w);
  316.     RotateBottomLeft(w);
  317.   }
  318.  
  319.   /* put the piece in place */
  320.   if (Side(w, 4, 3) == top_color) {
  321.     RotateFrontCw(w);
  322.     RotateCenterRight(w);
  323.     RotateCenterRight(w);
  324.     RotateFrontCcw(w);
  325.   } else {
  326.     RotateFrontCcw(w);
  327.     RotateCenterRight(w);
  328.     RotateFrontCw(w);
  329.   }
  330. }
  331.  
  332. /* This procedure solves the top (BLUE) side, except for one edge. */
  333. static void SolveTop(w)
  334.   RubikWidget w;
  335. {
  336.   int corner, edge;
  337.  
  338.   /* put the blue face on the top */
  339.   if (Side(w, 1, 4) == BLUE)
  340.     RotateUp(w);
  341.   else if (Side(w, 2, 4) == BLUE)
  342.     RotateCcw(w);
  343.   else if (Side(w, 3, 4) == BLUE)
  344.     RotateDown(w);
  345.   else if (Side(w, 4, 4) == BLUE)
  346.     RotateCw(w);
  347.   else if (Side(w, 6, 4) == BLUE) {
  348.     RotateUp(w);
  349.     RotateUp(w);
  350.   }
  351.  
  352.   /* first find the blue-red-white corner and place it */
  353.      corner = FindCorner(w,BLUE,RED,WHITE);
  354.   if (corner == 1) {
  355.     if (Side(w, 5, 6) == RED) {
  356.       RotateFrontCw(w);
  357.       RotateTopLeft(w);
  358.     } else if (Side(w, 5, 6) == WHITE) {
  359.       RotateLeftUp(w);
  360.       RotateTopRight(w);
  361.     }
  362.   } else if (corner == 2) {
  363.   if (Side(w, 5, 8) == BLUE)
  364.     RotateTopLeft(w);
  365.   else if (Side(w, 5, 8) == RED) {
  366.     RotateRightUp(w);
  367.     RotateTopLeft(w);
  368.     RotateTopLeft(w);
  369.   } else if (Side(w, 5, 8) == WHITE)
  370.     RotateFrontCcw(w);
  371.   } else if (corner == 3) {
  372.     if (Side(w, 5, 2) == BLUE) {
  373.       RotateTopLeft(w);
  374.       RotateTopLeft(w);
  375.     } else if (Side(w, 5, 2) == RED) {
  376.       RotateTopRight(w);
  377.       RotateLeftDown(w);
  378.     } else if (Side(w, 5, 2) == WHITE) {
  379.       RotateRightDown(w);
  380.       RotateTopLeft(w);
  381.     }
  382.   } else if (corner == 4) {
  383.     if (Side(w, 5, 0) == BLUE)
  384.       RotateTopRight(w);
  385.     else if (Side(w, 5, 0) == RED)
  386.       RotateLeftDown(w);
  387.     else if (Side(w, 5, 0) == WHITE) {
  388.       RotateTopRight(w);
  389.       RotateLeftUp(w);
  390.       RotateTopRight(w);
  391.     }
  392.   } else if (corner == 5) {
  393.     if (Side(w, 6, 0) == BLUE) {
  394.       RotateBottomLeft(w);
  395.       RotateLeftUp(w);
  396.       RotateLeftUp(w);
  397.     } else if (Side(w, 6, 0) == RED)
  398.       RotateLeftUp(w);
  399.     else if (Side(w, 6, 0) == WHITE)
  400.       RotateFrontCw(w);
  401.   } else if (corner == 6) {
  402.     if (Side(w, 6, 2) == BLUE) {
  403.       RotateFrontCw(w);
  404.       RotateFrontCw(w);
  405.     } else if (Side(w, 6, 2) == RED) {
  406.       RotateBottomLeft(w);
  407.       RotateLeftUp(w);
  408.     } else if (Side(w, 6, 2) == WHITE) {
  409.       RotateBottomLeft(w);
  410.       RotateFrontCw(w);
  411.     }
  412.   } else if (corner == 7) {
  413.     if (Side(w, 6, 8) == BLUE) {
  414.       RotateBottomLeft(w);
  415.       RotateFrontCw(w);
  416.       RotateFrontCw(w);
  417.     } else if (Side(w, 6, 8) == RED) {
  418.       RotateBottomLeft(w);
  419.       RotateBottomLeft(w);
  420.       RotateLeftUp(w);
  421.     } else if (Side(w, 6, 8) == WHITE) {
  422.       RotateBottomLeft(w);
  423.       RotateBottomLeft(w);
  424.       RotateFrontCw(w);
  425.     }
  426.   } else if (corner == 8) {
  427.     if (Side(w, 6, 6) == BLUE) {
  428.       RotateLeftUp(w);
  429.       RotateLeftUp(w);
  430.     } else if (Side(w, 6, 6) == RED) {
  431.       RotateBottomRight(w);
  432.       RotateLeftUp(w);
  433.     } else if (Side(w, 6, 6) == WHITE) {
  434.       RotateBottomRight(w);
  435.       RotateFrontCw(w);
  436.     }
  437.   }
  438.  
  439.   /* now find the blue-yellow-red corner and place it */
  440.   RotateLeft(w);
  441.   corner = FindCorner(w,BLUE,YELLOW,RED);
  442.   if (corner == 1) {
  443.     if (Side(w, 5, 6) == YELLOW) {
  444.       RotateFrontCcw(w);
  445.       RotateBottomRight(w);
  446.       RotateFrontCcw(w);
  447.       RotateFrontCcw(w);
  448.     } else if (Side(w, 5, 6) == RED) {
  449.       RotateFrontCw(w);
  450.       RotateFrontCw(w);
  451.       RotateBottomLeft(w);
  452.       RotateFrontCw(w);
  453.     }
  454.   } else if (corner == 2) {
  455.     if (Side(w, 5, 8) == BLUE) {
  456.       RotateRightDown(w);
  457.       RotateBottomLeft(w);
  458.       RotateFrontCw(w);
  459.     } else if (Side(w, 5, 8) == YELLOW) {
  460.       RotateRightDown(w);
  461.       RotateFrontCw(w);
  462.       RotateFrontCw(w);
  463.     } else if (Side(w, 5, 8) == RED)
  464.       RotateFrontCcw(w);
  465.   } else if (corner == 3) {
  466.     if (Side(w, 5, 2) == BLUE) {
  467.       RotateRightDown(w);
  468.       RotateRightDown(w);
  469.       RotateFrontCw(w);
  470.       RotateFrontCw(w);
  471.     } else if (Side(w, 5, 2) == YELLOW) {
  472.       RotateRightDown(w);
  473.       RotateFrontCcw(w);
  474.     } else if (Side(w, 5, 2) == RED) {
  475.       RotateRightDown(w);
  476.       RotateRightDown(w);
  477.       RotateBottomLeft(w);
  478.       RotateFrontCw(w);
  479.     }
  480.   } else if (corner == 5) {
  481.     if (Side(w, 6, 0) == BLUE) {
  482.       RotateBottomRight(w);
  483.       RotateFrontCw(w);
  484.       RotateFrontCw(w);
  485.     } else if (Side(w, 6, 0) == YELLOW) {
  486.       RotateBottomRight(w);
  487.       RotateRightUp(w);
  488.       RotateFrontCcw(w);
  489.     } else if (Side(w, 6, 0) == RED)
  490.       RotateFrontCw(w);
  491.   } else if (corner == 6) {
  492.     if (Side(w, 6, 2) == BLUE) {
  493.       RotateFrontCw(w);
  494.       RotateFrontCw(w);
  495.     } else if (Side(w, 6, 2) == YELLOW) {
  496.       RotateRightUp(w);
  497.       RotateFrontCcw(w);
  498.     } else if (Side(w, 6, 2) == RED) {
  499.       RotateBottomLeft(w);
  500.       RotateFrontCw(w);
  501.     }
  502.   } else if (corner == 7) {
  503.     if (Side(w, 6, 8) == BLUE) {
  504.       RotateBottomLeft(w);
  505.       RotateFrontCw(w);
  506.       RotateFrontCw(w);
  507.     } else if (Side(w, 6, 8) == YELLOW) {
  508.       RotateBottomLeft(w);
  509.       RotateRightUp(w);
  510.       RotateFrontCcw(w);
  511.     } else if (Side(w, 6, 8) == RED) {
  512.       RotateBottomLeft(w);
  513.       RotateBottomLeft(w);
  514.       RotateFrontCw(w);
  515.     }
  516.   } else if (corner == 8) {
  517.     if (Side(w, 6, 6) == BLUE) {
  518.       RotateBottomRight(w);
  519.       RotateBottomRight(w);
  520.       RotateFrontCw(w);
  521.       RotateFrontCw(w);
  522.     } else if (Side(w, 6, 6) == YELLOW) {
  523.       RotateBottomRight(w);
  524.       RotateBottomRight(w);
  525.       RotateRightUp(w);
  526.       RotateFrontCcw(w);
  527.     } else if (Side(w, 6, 6) == RED) {
  528.       RotateBottomRight(w);
  529.       RotateFrontCw(w);
  530.     }
  531.   }
  532.  
  533.   /* now find the blue-orange-yellow corner and place it */
  534.   RotateLeft(w);
  535.   corner = FindCorner(w,BLUE,ORANGE,YELLOW);
  536.   if (corner == 1) {
  537.     if (Side(w, 5, 6) == ORANGE) {
  538.       RotateFrontCcw(w);
  539.       RotateBottomRight(w);
  540.       RotateFrontCcw(w);
  541.       RotateFrontCcw(w);
  542.     } else if (Side(w, 5, 6) == YELLOW) {
  543.       RotateFrontCw(w);
  544.       RotateFrontCw(w);
  545.       RotateBottomLeft(w);
  546.       RotateFrontCw(w);
  547.     }
  548.   } else if (corner == 2) {
  549.     if (Side(w, 5, 8) == BLUE) {
  550.       RotateRightDown(w);
  551.       RotateBottomLeft(w);
  552.       RotateRightUp(w);
  553.       RotateFrontCw(w);
  554.     } else if (Side(w, 5, 8) == ORANGE) {
  555.       RotateFrontCw(w);
  556.       RotateBottomLeft(w);
  557.       RotateFrontCw(w);
  558.     } else if (Side(w, 5, 8) == YELLOW)
  559.       RotateFrontCcw(w);
  560.   } else if (corner == 5) {
  561.     if (Side(w, 6, 0) == BLUE) {
  562.       RotateBottomRight(w);
  563.       RotateFrontCw(w);
  564.       RotateFrontCw(w);
  565.     } else if (Side(w, 6, 0) == ORANGE) {
  566.       RotateRightDown(w);
  567.       RotateBottomRight(w);
  568.       RotateRightUp(w);
  569.       RotateFrontCcw(w);
  570.     } else if (Side(w, 6, 0) == YELLOW)
  571.       RotateFrontCw(w);
  572.   } else if (corner == 6) {
  573.     if (Side(w, 6, 2) == BLUE) {
  574.       RotateFrontCw(w);
  575.       RotateFrontCw(w);
  576.     } else if (Side(w, 6, 2) == ORANGE) {
  577.       RotateBottomLeft(w);
  578.       RotateRightDown(w);
  579.       RotateBottomRight(w);
  580.       RotateRightUp(w);
  581.       RotateFrontCcw(w);
  582.     } else if (Side(w, 6, 2) == YELLOW) {
  583.       RotateBottomLeft(w);
  584.       RotateFrontCw(w);
  585.     }
  586.   } else if (corner == 7) {
  587.     if (Side(w, 6, 8) == BLUE) {
  588.       RotateBottomLeft(w);
  589.       RotateFrontCw(w);
  590.       RotateFrontCw(w);
  591.     } else if (Side(w, 6, 8) == ORANGE) {
  592.       RotateBottomLeft(w);
  593.       RotateBottomLeft(w);
  594.       RotateRightDown(w);
  595.       RotateBottomRight(w);
  596.       RotateRightUp(w);
  597.       RotateFrontCcw(w);
  598.     } else if (Side(w, 6, 8) == YELLOW) {
  599.       RotateBottomLeft(w);
  600.       RotateBottomLeft(w);
  601.       RotateFrontCw(w);
  602.     }
  603.   } else if (corner == 8) {
  604.     if (Side(w, 6, 6) == BLUE) {
  605.       RotateBottomRight(w);
  606.       RotateBottomRight(w);
  607.       RotateFrontCw(w);
  608.       RotateFrontCw(w);
  609.     } else if (Side(w, 6, 6) == ORANGE) {
  610.       RotateRightDown(w);
  611.       RotateBottomRight(w);
  612.       RotateBottomRight(w);
  613.       RotateRightUp(w);
  614.       RotateFrontCcw(w);
  615.     } else if (Side(w, 6, 6) == YELLOW) {
  616.       RotateBottomRight(w);
  617.       RotateFrontCw(w);
  618.     }
  619.   }
  620.  
  621.   /* and now find the blue-white-orange corner and place it */
  622.   RotateLeft(w);
  623.   corner = FindCorner(w,BLUE,WHITE,ORANGE);
  624.   if (corner == 1) {
  625.     if (Side(w, 5, 6) == WHITE) {
  626.       RotateLeftDown(w);
  627.       RotateBottomRight(w);
  628.       RotateLeftUp(w);
  629.       RotateBottomLeft(w);
  630.       RotateBottomLeft(w);
  631.       RotateFrontCcw(w);
  632.       RotateBottomRight(w);
  633.       RotateFrontCw(w);
  634.     } else if (Side(w, 5, 6) == ORANGE) {
  635.       RotateFrontCcw(w);
  636.       RotateBottomLeft(w);
  637.       RotateFrontCw(w);
  638.       RotateBottomRight(w);
  639.       RotateBottomRight(w);
  640.       RotateLeftDown(w);
  641.       RotateBottomLeft(w);
  642.       RotateLeftUp(w);
  643.     }
  644.   } else if (corner == 5) {
  645.     if (Side(w, 6, 0) == BLUE) {
  646.       RotateBottomRight(w);
  647.       RotateLeftDown(w);
  648.       RotateBottomLeft(w);
  649.       RotateBottomLeft(w);
  650.       RotateLeftUp(w);
  651.       RotateBottomRight(w);
  652.       RotateLeftDown(w);
  653.       RotateBottomLeft(w);
  654.       RotateLeftUp(w);
  655.     } else if (Side(w, 6, 0) == WHITE) {
  656.       RotateBottomRight(w);
  657.       RotateLeftDown(w);
  658.       RotateBottomLeft(w);
  659.       RotateLeftUp(w);
  660.     } else if (Side(w, 6, 0) == ORANGE) {
  661.       RotateBottomLeft(w);
  662.       RotateFrontCcw(w);
  663.       RotateBottomRight(w);
  664.       RotateFrontCw(w);
  665.     }
  666.   } else if (corner == 6) {
  667.     if (Side(w, 6, 2) == BLUE) {
  668.       RotateBottomRight(w);
  669.       RotateFrontCcw(w);
  670.       RotateBottomLeft(w);
  671.       RotateFrontCw(w);
  672.       RotateBottomLeft(w);
  673.       RotateFrontCcw(w);
  674.       RotateBottomRight(w);
  675.       RotateFrontCw(w);
  676.     } else if (Side(w, 6, 2) == WHITE) {
  677.       RotateLeftDown(w);
  678.       RotateBottomLeft(w);
  679.       RotateLeftUp(w);
  680.     } else if (Side(w, 6, 2) == ORANGE) {
  681.       RotateBottomLeft(w);
  682.       RotateBottomLeft(w);
  683.       RotateFrontCcw(w);
  684.       RotateBottomRight(w);
  685.       RotateFrontCw(w);
  686.     }
  687.   } else if (corner == 7) {
  688.     if (Side(w, 6, 8) == BLUE) {
  689.       RotateLeftDown(w);
  690.       RotateBottomRight(w);
  691.       RotateLeftUp(w);
  692.       RotateBottomRight(w);
  693.       RotateLeftDown(w);
  694.       RotateBottomLeft(w);
  695.       RotateLeftUp(w);
  696.     } else if (Side(w, 6, 8) == WHITE) {
  697.       RotateLeftDown(w);
  698.       RotateBottomLeft(w);
  699.       RotateBottomLeft(w);
  700.       RotateLeftUp(w);
  701.     } else if (Side(w, 6, 8) == ORANGE) {
  702.       RotateFrontCcw(w);
  703.       RotateBottomLeft(w);
  704.       RotateBottomLeft(w);
  705.       RotateFrontCw(w);
  706.     }
  707.   } else if (corner == 8) {
  708.     if (Side(w, 6, 6) == BLUE) {
  709.       RotateFrontCcw(w);
  710.       RotateBottomRight(w);
  711.       RotateBottomRight(w);
  712.       RotateFrontCw(w);
  713.       RotateBottomLeft(w);
  714.       RotateFrontCcw(w);
  715.       RotateBottomRight(w);
  716.       RotateFrontCw(w);
  717.     } else if (Side(w, 6, 6) == WHITE) {
  718.       RotateBottomRight(w);
  719.       RotateBottomRight(w);
  720.       RotateLeftDown(w);
  721.       RotateBottomLeft(w);
  722.       RotateLeftUp(w);
  723.     } else if (Side(w, 6, 6) == ORANGE) {
  724.       RotateFrontCcw(w);
  725.       RotateBottomRight(w);
  726.       RotateFrontCw(w);
  727.     }
  728.   }
  729.   RotateLeft(w);
  730.  
  731.   /* find the blue-red edge and place it */
  732.   edge = FindEdge(w,BLUE,RED);
  733.   PlaceEdge(w,edge,BLUE);
  734.   RotateLeft(w);
  735.  
  736.   /* find the blue-yellow edge and place it */
  737.   edge = FindEdge(w,BLUE,YELLOW);
  738.   PlaceEdge(w,edge,BLUE);
  739.   RotateLeft(w);
  740.  
  741.   /* find the blue-orange edge and place it */
  742.   edge = FindEdge(w,BLUE,ORANGE);
  743.   PlaceEdge(w,edge,BLUE);
  744.   RotateLeft(w);
  745.  
  746.   RotateUp(w);     /* put the blue side to the back */
  747. }
  748.  
  749. /* This procedure places the front (GREEN) four corners into */
  750. /* their correct positions. */
  751. static void AlignCorners(w)
  752.   RubikWidget w;
  753. {
  754.   int corner;
  755.  
  756.   /* find and place the green-orange-white corner (upper left) */
  757.   corner = FindCorner(w,GREEN,ORANGE,WHITE);
  758.   if (corner == 2)
  759.     RotateFrontCcw(w);
  760.   else if (corner == 5)
  761.     RotateFrontCw(w);
  762.   else if (corner == 6) {
  763.     RotateFrontCw(w);
  764.     RotateFrontCw(w);
  765.   }
  766.  
  767.   /* find and place the green-yellow-orange corner (lower left) */
  768.   corner = FindCorner(w,GREEN,YELLOW,ORANGE);
  769.   if (corner == 2) {
  770.     RotateCw(w);
  771.     SwapBottomCorners(w);
  772.     RotateCcw(w);
  773.     SwapBottomCorners(w);
  774.   } else if (corner == 6)
  775.     SwapBottomCorners(w);
  776.  
  777.   /* find and place the green-red-yellow corner (lower right) */
  778.   corner = FindCorner(w,GREEN,RED,YELLOW);
  779.   if (corner == 2) {
  780.     RotateCw(w);
  781.     SwapBottomCorners(w);
  782.     RotateCcw(w);
  783.   }
  784. }
  785.  
  786. /* This procedure swaps the the bottom front corners. */
  787. static void SwapBottomCorners(w)
  788.   RubikWidget w;
  789. {
  790.   RotateTopRight(w);
  791.   RotateFrontCw(w);
  792.   RotateTopLeft(w);
  793.   RotateLeftUp(w);
  794.   RotateTopLeft(w);
  795.   RotateLeftDown(w);
  796.   RotateTopRight(w);
  797.   RotateFrontCw(w);
  798.   RotateFrontCw(w);
  799. }
  800.  
  801. /* This procedure completes the GREEN side by color-aligning the GREEN */
  802. /* corners and putting the GREEN edges in place. */
  803. static void SolveBottom(w)
  804.   RubikWidget w;
  805. {
  806.   int aligned;
  807.  
  808.   /* the GREEN corners (currently in the front) should now be in their */
  809.   /* proper locations; next, we color align them, and then move the */
  810.   /* bottom edges into place */
  811.   do {
  812.     aligned = 0;
  813.     if (Side(w, 1, 0) == GREEN)
  814.       aligned++;
  815.     if (Side(w, 1, 2) == GREEN)
  816.       aligned++;
  817.     if (Side(w, 1, 6) == GREEN)
  818.       aligned++;
  819.     if (Side(w, 1, 8) == GREEN)
  820.       aligned++;
  821.  
  822.     if (aligned == 0) {
  823.       ColorAlignFront(w);
  824.     } else if (aligned == 1) {
  825.       /* place aligned corner in upper right */
  826.       if (Side(w, 1, 0) == GREEN)
  827.       RotateFrontCw(w);
  828.       if (Side(w, 1, 6) == GREEN) {
  829.         RotateFrontCw(w);
  830.         RotateFrontCw(w);
  831.       }
  832.       if (Side(w, 1, 8) == GREEN)
  833.         RotateFrontCcw(w);
  834.       ColorAlignFront(w);
  835.     } else if (aligned == 2) {
  836.       if (Side(w, 1, 0) != GREEN)
  837.         RotateFrontCw(w);
  838.       else if (Side(w, 1, 2) == GREEN)
  839.         RotateFrontCw(w);
  840.       if (Side(w, 1, 0) != GREEN)
  841.         RotateFrontCw(w);
  842.       ColorAlignFront(w);
  843.     } else if (aligned == 3) /* not sure if this is possible */
  844.       ColorAlignFront(w);
  845.   } while (aligned < 4);
  846. }
  847.  
  848. static void Solve_2_2(w)
  849.   RubikWidget w;
  850. {
  851.   int i;
  852.  
  853.   for (i = 0; i < 3; i++) /* This is not always efficient */
  854.     if (!CheckSolved(w))
  855.       RotateFrontCw(w);
  856. }
  857.  
  858. static void SolveBottomEdges(w)
  859.   RubikWidget w;
  860. {
  861.   int edge, color;
  862.  
  863.   /* next we move the bottom edges into place */
  864.   RotateDown(w);        /* put the green face on top */
  865.   RotateCw(w);
  866.   RotateCw(w);
  867.  
  868.   color = Side(w, 1, 0);     /* get upper front corner color */
  869.   edge = FindEdge(w,GREEN,color);
  870.   PlaceEdge(w,edge,GREEN);
  871.   RotateTopRight(w);
  872.  
  873.   color = Side(w, 1, 0);     /* get upper front corner color */
  874.   edge = FindEdge(w,GREEN,color);
  875.   PlaceEdge(w,edge,GREEN);
  876.   RotateTopRight(w);
  877.  
  878.   color = Side(w, 1, 0);     /* get upper front corner color */
  879.   edge = FindEdge(w,GREEN,color);
  880.   PlaceEdge(w,edge,GREEN);
  881.   RotateTopRight(w);
  882.  
  883.   color = Side(w, 1, 0);     /* get upper front corner color */
  884.   edge = FindEdge(w,GREEN,color);
  885.   PlaceEdge(w,edge,GREEN);
  886.   RotateTopRight(w);
  887.  
  888.   /* now, align the fourth blue edge piece (if necessary) */
  889.   RotateCw(w);
  890.   RotateCw(w);
  891.   edge = FindEdge(w,BLUE,WHITE);
  892.   if (edge == 1) {
  893.     if (Side(w, 1, 1) == BLUE) {
  894.       RotateFrontCcw(w);
  895.       RotateCenterLeft(w);
  896.       RotateFrontCw(w);
  897.       RotateCenterLeft(w);
  898.       RotateFrontCw(w);
  899.       RotateCenterLeft(w);
  900.       RotateFrontCcw(w);
  901.     }
  902.   } else {
  903.     if (edge == 5)
  904.       RotateCenterRight(w);
  905.     else if (edge == 7)
  906.       RotateCenterLeft(w);
  907.     else if (edge == 8) {
  908.       RotateCenterRight(w);
  909.       RotateCenterRight(w);
  910.     }
  911.     AlignLastEdge(w);
  912.   }
  913. }
  914.  
  915. /* This procedure moves the remaining BLUE edge piece into position */
  916. /* from edge position #6. */
  917. static void AlignLastEdge(w)
  918.   RubikWidget w;
  919. {
  920.   /* edge piece should be in edge position #6 */
  921.   /* check its orientation and decide which sequence to perform */
  922.   if (Side(w, 1, 5) == BLUE) {
  923.     RotateCenterLeft(w);
  924.     RotateFrontCw(w);
  925.     RotateCenterRight(w);
  926.     RotateFrontCcw(w);
  927.     RotateCenterLeft(w);
  928.     RotateFrontCcw(w);
  929.     RotateCenterRight(w);
  930.     RotateFrontCw(w);
  931.   } else {
  932.     RotateFrontCcw(w);
  933.     RotateCenterLeft(w);
  934.     RotateFrontCw(w);
  935.     RotateCenterRight(w);
  936.     RotateFrontCw(w);
  937.     RotateCenterLeft(w);
  938.     RotateFrontCcw(w);
  939.   }
  940. }
  941.  
  942. /* This procedure aligns the bottom corner colors (may need to be repeated). */
  943. static void ColorAlignFront(w)
  944.   RubikWidget w;
  945. {
  946.   RotateTopRight(w);
  947.   RotateFrontCw(w);
  948.   RotateFrontCw(w);
  949.   RotateTopLeft(w);
  950.   RotateFrontCw(w);
  951.   RotateTopRight(w);
  952.   RotateFrontCw(w);
  953.   RotateTopLeft(w);
  954.   RotateFrontCw(w);
  955.   RotateFrontCw(w);
  956. }
  957.  
  958. /* This procedure completes the solution process by placing the */
  959. /* remaining edges in place and alignment. */
  960. static void AlignEdges(w)
  961.   RubikWidget w;
  962. {
  963.   int aligned, color, edge;
  964.  
  965.   /* move the red side to the front */
  966.   if (Side(w, 1, 4) == YELLOW)
  967.     RotateRight(w);
  968.   else if (Side(w, 1, 4) == ORANGE) {
  969.     RotateRight(w);
  970.     RotateRight(w);
  971.   } else if (Side(w, 1, 4) == WHITE)
  972.     RotateLeft(w);
  973.  
  974.   /* rotate the top until its aligned with the center colors */
  975.   edge = FindEdge(w,BLUE,RED);
  976.   if (edge == 2)
  977.     RotateTopLeft(w);
  978.   else if (edge == 3) {
  979.     RotateTopLeft(w);
  980.     RotateTopLeft(w);
  981.   } else if (edge == 4)
  982.     RotateTopRight(w);
  983.  
  984.   /* rotate the bottom until its aligned with the center colors */
  985.   edge = FindEdge(w,GREEN,RED);
  986.   if (edge == 10)
  987.     RotateBottomLeft(w);
  988.   else if (edge == 11) {
  989.     RotateBottomLeft(w);
  990.     RotateBottomLeft(w);
  991.   } else if (edge == 12)
  992.     RotateBottomRight(w);
  993.  
  994.   if (CheckSolved(w))
  995.     return;
  996.  
  997.   RotateCcw(w);  /* place unaligned edges vertically */
  998.  
  999.   /* see if any edges are in correct position */
  1000.   aligned = 0;
  1001.   edge = FindEdge(w,RED,YELLOW);
  1002.   if (edge == 1)
  1003.     aligned++;
  1004.   edge = FindEdge(w,YELLOW,ORANGE);
  1005.   if (edge == 3)
  1006.     aligned++;
  1007.   edge = FindEdge(w,ORANGE,WHITE);
  1008.   if (edge == 11)
  1009.     aligned++;
  1010.   edge = FindEdge(w,WHITE,RED);
  1011.   if (edge == 9)
  1012.     aligned++;
  1013.  
  1014.   if (aligned == 0) {
  1015.     ShuffleEdges(w);  /* put one edge into position */
  1016.     aligned++;
  1017.   }
  1018.  
  1019.   if (aligned == 1) {
  1020.     /* find the correct piece and move it to the back bottom edge */
  1021.     edge = FindEdge(w,RED,YELLOW);
  1022.     if (edge == 1) {
  1023.       RotateDown(w);
  1024.       RotateDown(w);
  1025.     } else {
  1026.       edge = FindEdge(w,YELLOW,ORANGE);
  1027.       if (edge == 3)
  1028.         RotateUp(w);
  1029.       else {
  1030.         edge = FindEdge(w,WHITE,RED);
  1031.         if (edge == 9)
  1032.           RotateDown(w);
  1033.       }
  1034.     }
  1035.  
  1036.     /* shuffle */
  1037.     color = Side(w, 1, 4);
  1038.     if (Side(w, 1, 7) == color) {
  1039.       RotateRight(w);
  1040.       RotateRight(w);
  1041.       RotateDown(w);
  1042.       ShuffleEdges(w);
  1043.     } else if (Side(w, 6, 1) == color) {
  1044.       RotateRight(w);
  1045.       RotateRight(w);
  1046.       RotateDown(w);
  1047.       ShuffleEdges(w);
  1048.     } else
  1049.       ShuffleEdges(w);
  1050.   }
  1051.  
  1052.   /* pieces should be in place; complete color alignment */
  1053.   /* find number of unaligned edge pieces and fix them */
  1054.   aligned = 0;
  1055.   if (Side(w, 1, 1) == Side(w, 1, 4))
  1056.     aligned++;
  1057.   if (Side(w, 1, 7) == Side(w, 1, 4))
  1058.     aligned++;
  1059.   if (Side(w, 3, 1) == Side(w, 3, 4))
  1060.     aligned++;
  1061.   if (Side(w, 3, 7) == Side(w, 3, 4))
  1062.     aligned++;
  1063.   if (aligned == 0) {
  1064.     RecolorTopEdges(w);
  1065.     RotateDown(w);
  1066.     RotateDown(w);
  1067.     RecolorTopEdges(w);
  1068.   } else if (aligned == 2) {
  1069.     if (Side(w, 1, 1) == Side(w, 1, 4))
  1070.       do {
  1071.         RotateDown(w);
  1072.       } while (Side(w, 1, 1) == Side(w, 1, 4));
  1073.     if (Side(w, 1, 7) != Side(w, 1, 4))
  1074.       RotateUp(w);
  1075.     RecolorTopEdges(w);
  1076.     if (!CheckSolved(w)) {
  1077.       RotateDown(w);
  1078.       RecolorTopEdges(w);
  1079.     }
  1080.   }
  1081. }
  1082.  
  1083. /* This procedure "shuffles" the three center edges on the front and */
  1084. /* top faces. */
  1085. static void ShuffleEdges(w)
  1086.   RubikWidget w;
  1087. {
  1088.   RotateCenterUp(w);
  1089.   RotateTopRight(w);
  1090.   RotateTopRight(w);
  1091.   RotateCenterDown(w);
  1092.   RotateTopRight(w);
  1093.   RotateTopRight(w);
  1094. }
  1095.  
  1096. /* This procedure should be used when the two opposing top front and back */
  1097. /* edge pieces are in position but not color aligned (this sequence is */
  1098. /* known as Rubik's Maneuver). */
  1099. static void RecolorTopEdges(w)
  1100.   RubikWidget w;
  1101. {
  1102.   RotateCenterUp(w);
  1103.   RotateTopRight(w);
  1104.   RotateCenterUp(w);
  1105.   RotateTopRight(w);
  1106.   RotateCenterUp(w);
  1107.   RotateTopRight(w);
  1108.   RotateTopRight(w);
  1109.   RotateCenterDown(w);
  1110.   RotateTopRight(w);
  1111.   RotateCenterDown(w);
  1112.   RotateTopRight(w);
  1113.   RotateCenterDown(w);
  1114.   RotateTopRight(w);
  1115.   RotateTopRight(w);
  1116. }
  1117.  
  1118. /* This procedure coordinates the solution process. */
  1119. void SolvePolyhedrons(w)
  1120.   RubikWidget w;
  1121. {
  1122.   rubikCallbackStruct cb;
  1123.  
  1124.   cb.reason = RUBIK_RESET;
  1125.   XtCallCallbacks((Widget) w, XtNselectCallback, &cb);
  1126.   if (!CheckSolved(w)) {
  1127.     SolveTop(w);
  1128.     AlignCorners(w);
  1129.     SolveBottom(w);
  1130.     if (w->rubik.size > 2) {
  1131.       SolveBottomEdges(w);
  1132.       AlignEdges(w);
  1133.     } else if (w->rubik.size == 2)
  1134.       Solve_2_2(w);
  1135.   }
  1136.   cb.reason = RUBIK_COMPUTED;
  1137.   XtCallCallbacks((Widget) w, XtNselectCallback, &cb);
  1138. }
  1139.